#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

struct Interval {
     int start;
     int end;
     Interval() : start(0), end(0) {}
     Interval(int s, int e) : start(s), end(e) {}
};

bool myComp(const Interval &lhs, const Interval &rhs)
{
    return lhs.start != rhs.start ? lhs.start < rhs.start : lhs.end < rhs.end;
}

class Solution {
    public:
        vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
            vector<Interval>::iterator iter = lower_bound(intervals.begin(), intervals.end(), newInterval, myComp);
            intervals.insert(iter, newInterval);
            vector<Interval> ans;
            int start = intervals[0].start;
            int end = intervals[0].end;
            for (int i = 1; i < intervals.size(); i++) {
                if (end < intervals[i].start) {
                    ans.push_back(Interval(start, end));
                    start = intervals[i].start;
                    end = intervals[i].end;
                } else {
                    end = max(intervals[i].end, end);
                }
            }
            ans.push_back(Interval(start, end));
            return ans;
        }
};

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    vector<Interval> myVec;
    myVec.push_back(Interval(1,2));
    myVec.push_back(Interval(3,5));
    myVec.push_back(Interval(6,7));
    myVec.push_back(Interval(8,10));
    myVec.push_back(Interval(12,16));
    vector<Interval> result = mySolution.insert(myVec, Interval(4,9));
    for (int i = 0; i < result.size(); i++) {
        cout << result[i].start << " " << result[i].end << endl;
    }

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
